package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 面试题 08.11. 硬币
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/1 15:36
 */
public class WaysToChange {


    public static void main(String[] args) {
        WaysToChange test = new WaysToChange();

        // 142511
//        int n = 1000;

        // 134235101
        int n = 10000;

        // 4
//        int n = 10;

        // 6
//        int n = 60;

        // 332576607
//        int n = 1000000;

        for (int i = 0; i < 100; i++) {
            int g = test.waysToChange(i);
            System.out.println(i + "   " + g);
        }

    }


    public int waysToChange(int n) {
        n /= 5;
        if (n < 2) {
            return n + 1;
        }
        long[] longs = new long[n + 1];
        longs[0] = 1;
        longs[1] = 1;
        for (int i = n + 2; i > 1; i--) {
            longs[i - 2] = ((long) i - (i >> 1)) * (i >> 1) % 1000000007;
        }
        if (n < 5) {
            return (int) longs[n];
        }
        for (int i = 5; i <= n; i++) {
            longs[i] = (longs[i] + longs[i - 5]) % 1000000007;
        }
        return (int) longs[n];
    }


}
